//字母迷宫游戏初始界面记作 m x n 二维字符串数组 grid，请判断玩家是否能在 grid 中找到目标单词 target。 注意：寻找单词时 必须 按照字
//母顺序，通过水平或垂直方向相邻的单元格内的字母构成，同时，同一个单元格内的字母 不允许被重复使用 。 
//
// 
//
// 
//
// 
//
// 示例 1： 
//
// 
//输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = 
//"ABCCED"
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = 
//"SEE"
//输出：true
// 
//
// 示例 3： 
//
// 
//输入：grid = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], target = 
//"ABCB"
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// m == grid.length 
// n = grid[i].length 
// 1 <= m, n <= 6 
// 1 <= target.length <= 15 
// grid 和 target 仅由大小写英文字母组成 
// 
//
// 
//
// 注意：本题与主站 79 题相同：https://leetcode-cn.com/problems/word-search/ 
//
// 
//
// 
//
// Related Topics 数组 字符串 回溯 矩阵 👍 846 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-04-26 13:40:36
 * @description LCR 129.字母迷宫
 */
public class JuZhenZhongDeLuJingLcof{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 JuZhenZhongDeLuJingLcof fun=new JuZhenZhongDeLuJingLcof();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 boolean [][] vis;
		 int [] dx={-1,0,1,0};
		 int [] dy={0,1,0,-1};
    public boolean wordPuzzle(char[][] grid, String target) {
		int m = grid.length;
		int n = grid[0].length;
		vis=new boolean[m][n];
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if(grid[i][j]==target.charAt(0)){
					vis[i][j]=true;
					if(dfs(grid,i,j,target,1)){
						return true;
					}
					vis[i][j]=false;
				}
			}
		}
		return false;
	}
	private boolean dfs(char [][] grid,int x,int y,String target,int idx){
		if(idx==target.length()) return true;
		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (nx >= 0 && nx < grid.length && ny >= 0 && ny < grid[0].length
					&& !vis[nx][ny] && grid[nx][ny] == target.charAt(idx)) {
				vis[nx][ny] = true;
				if (dfs(grid, nx, ny, target, idx + 1)) {
					return true;
				}
				vis[nx][ny] = false;
			}
		}
		return false;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
